Dynamic Programming
動態規劃 Dynamic Programming :
idea : 動態規劃(Dynamic Programming)是指將一個較大的問題定義為較小的子問題組合，先處理較小的問題並將結果儲存起來(通常使用表格)，再進一步以較小問題的解逐步建構出較大問題的解。
Easy solution in Fibonacci Squence or Leetcode(70 :Climbing Stairs.)
- First we can do it in recusive part, but no memory save.
The time limit exceeded!
Because we do more time in the repeated work, and the Time Complexity is $O(2^n)$.
- we can do in the memory part, recursive.
Time Complexity is O(n). - we can do the DP(Dynamic programming).
經典動態規劃問題
- Shortest path problem in weighted directed graph (negative edge allowed but no negative cycles)
Question : Find the minimum path in th graph
approch : (forward or backward)
Here is the forward DP
let $f(k)$ is the shortest path to the k point.
$f(k) = 0$
$W(k-1,k)$ is the distance from $k-1$ to $k$
recursive with $f(k-1) = min{f(k) + W(k-1,k)}$
Time Complexity : O(|V|+|E|)
The Longest Common Subsequence (LCS) Problem:
Question : Give two Sequences $X = <x_1,x_2,….x_n>, Y = <y_1,y_2,…y_m>$ find the Longest common subsequence(words not need to consecutive)
solution :
example for LCS